题目链接
链接
题解
用\(k\)进制串替换\(n\)个单词，还要有唯一性，并且要求最值。如果学过哈夫曼树的话套个模板就能出来……？
裸的 k 叉哈夫曼树，每次从森林中提取出权值前\(k\)小棵树构造新树，最后只剩\(1\)棵树即可。
由于最开始有\(n\)棵树，最后剩\(1\)棵树，每次删去\(k\)棵树，加进去\(1\)棵树，可得\((k-1)|(n-1)\)，如果节点不能整除可以补几个权值为\(1\)的虚拟节点。
可以用优先队列+结构体实现，排序时以权值为第一关键字，深度为第二关键字。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
typedef double db;
inline LL read()
{
LL x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
int n,k;
struct node
{
LL val;
int dep;
bool operator<(const node b)const
{
return val==b.val?dep>b.dep:val>b.val;
}
void clear()
{
val=dep=0;
}
}ans,tmp1,tmp2;
priority_queue<node>q;
int main()
{
n=read();k=read();
for(int i=1;i<=n;++i)
{
tmp1.val=read();
q.push(tmp1);
}
if(k>2)
{
while(n%(k-1)!=1)
{
q.push(tmp2);
++n;
}
}
while(q.size()!=1)
{
tmp2.clear();
for(int i=1;i<=k;++i)
{
tmp1=q.top();
q.pop();
tmp2.val+=tmp1.val;
tmp2.dep=max(tmp2.dep,tmp1.dep+1);
}
ans.val+=tmp2.val;
ans.dep=max(ans.dep,tmp2.dep);
q.push(tmp2);
}
printf("%lld\n%d\n",ans.val,ans.dep);
return 0;
}
|